/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/interval-minimum-number
@Language: C++
@Datetime: 16-02-09 05:55
*/

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
class Solution { 
    struct LineNode{
        long long val;
        int start,end;
        LineNode *left,*right;
        LineNode(long long val,int start,int end){
            this->val = val,this->start=start,this->end=end;
            left = right = NULL;
        }
    };
    LineNode *build(vector<int> &A,int start,int end){
        if (start>end)
            return NULL;
        LineNode *ln = new LineNode(A[start],start,end);
        if (start==end)
            return ln;
        ln->left = build(A,start,(end-start)/2+start);
        ln->right= build(A,(end-start)/2+start+1,end);
        ln->val = (ln->left->val < ln->right->val ? 
                ln->left->val : ln->right->val);
        return ln;
    }
    long long query(LineNode *ln,int start,int end){
        if (ln==NULL)
            return 0;
        if (ln->start == start && ln->end == end)
            return ln->val;
        int mid = ln->start + (ln->end - ln->start)/2;
        if (start > mid)
            return query(ln->right,start,end);
        if (end <= mid)
            return query(ln->left,start,end);
        long long left = query(ln->left,start,mid);
        long long right = query(ln->right,mid+1,end);
        return (left<right?left:right);
    }
    void destroy(LineNode *ln){
        if (ln==NULL)
            return;
        destroy(ln->left);
        destroy(ln->right);
        delete ln;
    }
public:
    /**
     *@param A, queries: Given an integer array and an query list
     *@return: The result list
     */
    vector<int> intervalMinNumber(vector<int> &A, vector<Interval> &queries) {
        // write your code here
        LineNode *ln = build(A,0,A.size()-1);
        vector<int> vs;
        for(int i=0;i<queries.size();++i)
            vs.push_back(query(ln,queries[i].start,queries[i].end));
        destroy(ln);
        return vs;
    }
};